package tree.ordertraversal;

import tree.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @Classname : BinaryTreePreorderTraversal
 * @Description :
 * <a href="https://leetcode.cn/problems/binary-tree-preorder-traversal/">144. 二叉树的前序遍历</a>
 * @Author : chentianyu
 * @Date 2023/1/8 21:11
 */


public class BinaryTreePreorderTraversal {

    /**
     * 栈循环实现前序遍历
     *
     * @param root
     * @return
     */
    public List<Integer> preorderTraversal2(TreeNode root) {
        List<Integer> preorder = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if (root != null) stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            preorder.add(cur.val);
            // 注意先序遍历优先遍历左子节点，因此先把右子节点压栈
            if (cur.right != null) stack.push(cur.right);
            if (cur.left != null) stack.push(cur.left);
        }
        return preorder;
    }


    /**
     * 递归实现前序遍历
     *
     * @param root
     * @return
     */
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> preorder = new ArrayList<>();
        preorderTraversalHelper(preorder, root);
        return preorder;
    }

    private void preorderTraversalHelper(List<Integer> preorder, TreeNode cur) {
        if (cur == null) return;

        preorder.add(cur.val);
        preorderTraversalHelper(preorder, cur.left);
        preorderTraversalHelper(preorder, cur.right);
    }
}
